The present invention relates to techniques for selecting links when setting up paths in transport networks.
The current generation of transport network equipment provides the ability to set up explicit paths in a network by employing various kinds of signalling mechanisms. The network typically consists of nodes—more particularly, cross-connects—interconnected by transport links. For example, a link can be an STS-48 link, containing 48 STS-1 channels. There can be multiple links connecting a pair of cross-connects to form a logical aggregated link. Each link contains multiple bi-directional channels. Connections, such as connection-oriented data streams or TDM circuits, are routed through the network via the cross-connects, wherein each cross-connect routes the data contained in a connection from a set of incoming channels to a set of outgoing channels. The choice of which output channels to transfer the data to depends on a combination of factors such as the identity of incoming channels, header bits, timeslots, wavelengths, etc. Examples of cross-connects include IP routers with MPLS capabilities, digital cross connects, and photonic switches. A few examples of signalling mechanisms for path set-up are RSVP, CR-LDP, and ATM signalling.
A connection is routed over a sequence of cross-connects and selected adjacent links. Consider, for example, a SONET-like network where every connection is assigned a set of channels and each channel belongs to at most one connection. We assume that all the channels assigned to a connection within a single aggregated link must be on a single link. However, channels belonging to a connection within a link do not have to be contiguous.
To set up a connection, first the routing or the management system computes a sequence of cross-connects as a path. Then the signalling system reserves, and ultimately assigns, a set of channels (according to the bandwidth requirement of the connection) between each pair of cross-connects on this path.
There are at least two well-known schemes for link selection. A first one of these is the so-called Best-first algorithm. The Best-fit algorithm chooses the link with the least amount of spare bandwidth that can accommodate a requested connection. Studies have shown that this algorithm is generally the best way to select the links to minimize bandwidth fragmentation. That is, it preserves links with large amount of channels available so that those links can later accommodate requests to set up connections that require a large amount of bandwidth.
Unfortunately, the Best-fit algorithm performs poorly in avoiding the well-known protocol problem known as “glare.” Glare may arise when two connection-set-up messages traveling in opposite directions try to reserve the same bi-directional channels, even if other channels and links are available. The first set-up attempt reserves a set of channels on one end of the link and meanwhile, the message traveling in the opposite direction reserves some of these channels on the other end of the same link. Both messages, when they try to reserve the channels on their other ends, find that the channels have already been reserved by another connection and therefore the message is returned as “unsuccessful.”
A second scheme for link selection is called Hi-Lo. In the Hi-Lo algorithm every pair of adjacent cross-connects predetermines an ordering of the links connecting them. Then one cross-connect examines all of the links in the decreasing index order and picks the first link that can accommodate the connection. The other cross-connect examines the links in increasing index order and picks the first link that can accommodate the connection. This scheme works very well for glare. However, it makes no attempt to minimize fragmentation and, indeed, can lead to a situation wherein there are only a few links whose bandwidth is not fragmented.
One possible approach for avoiding glare while minimizing fragmentation, is for each pair of neighbouring cross-connect interfaces to select one cross-connect interface as “master” and the other as “slave”. The master cross-connect interface is responsible for selecting channels for connections traveling in either direction using, for example, the Best-fit algorithm. If the connection is traveling from master towards the slave cross-connect, the master cross-connect can select links and channels and convey this to the slave cross-connect. For connections traveling from slave to the master cross-connect, an extra signalling message conveying the link/channel selection from master to slave is needed. Disadvantageously, this approach engenders additional signalling overhead.